Binary Tree & BST

contents

이진 트리(Binary Tree) 와 이진 탐색 트리(Binary Search Tree, BST) 의 상세한 분석, 둘의 차이점, 그리고 이것들이 왜 중요한지에 대한 설명입니다.

1부: 이진 트리 (기초 단계)

이진 트리는 계층적인 데이터 구조입니다. 선형적인 배열이나 연결 리스트와 달리, 트리는 나뭇가지처럼 뻗어 나갑니다.

"이진(Binary)"이라는 단어는 단순히 "두 개" 를 의미합니다. 이진 트리에서 모든 데이터(이를 노드(Node) 라고 부름)는 최대 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 가질 수 있습니다.

1. 트리의 구조 (해부학)

• 루트 (Root): 트리의 맨 꼭대기에 있는 노드입니다. 루트는 단 하나만 존재합니다.
• 간선 (Edge): 두 노드를 연결하는 선입니다.
• 부모/자식 (Parent/Child): 아래로 뻗어나가는 가지를 가진 노드가 부모입니다. 그 아래에 연결된 노드들이 자식입니다.
• 단말 노드 / 리프 (Leaf): 자식이 하나도 없는 노드입니다 (트리의 맨 밑바닥).
• 높이 (Height): 루트에서 가장 깊은 리프 노드까지 도달하는 데 거치는 가장 긴 경로의 간선 개수입니다.

2. 이진 트리의 종류

모든 이진 트리가 같은 모양을 하고 있는 것은 아닙니다. 트리의 모양이 효율성을 결정합니다.

• 정 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식을 가집니다. (외동자식이 없음).
• 완전 이진 트리 (Complete Binary Tree): 트리의 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 차례대로 채워져 있습니다.
• 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 정확히 두 개의 자식을 가지고 있으며, 모든 리프 노드가 정확히 같은 레벨(깊이)에 있습니다. (완벽하게 대칭인 삼각형 모양).

3. 트리 순회 (데이터를 읽는 방법)

트리는 선형적이지 않기 때문에, 단순히 왼쪽에서 오른쪽으로 읽을 수 없습니다. 모든 노드를 방문하기 위해 "순회(Traversals)"라는 방법을 사용합니다.

• 중위 순회 (In-order: 왼쪽, 루트, 오른쪽): 왼쪽 가지를 읽고, 부모를 읽고, 오른쪽 가지를 읽습니다. (이진 탐색 트리에서 오름차순으로 데이터를 읽을 때 사용).
• 전위 순회 (Pre-order: 루트, 왼쪽, 오른쪽): 부모를 먼저 읽고 자식을 읽습니다. 트리의 복사본을 만들 때 주로 사용합니다.
• 후위 순회 (Post-order: 왼쪽, 오른쪽, 루트): 자식을 먼저 읽고 부모를 마지막에 읽습니다. 트리를 삭제할 때 사용합니다 (부모를 지우기 전에 자식을 먼저 지워야 하므로).

2부: 이진 탐색 트리 (똑똑한 트리)

일반적인 이진 트리는 데이터가 어디에 들어가야 하는지에 대한 규칙이 없습니다. 일반 이진 트리에서 숫자 15를 찾으려면, 찾을 때까지 모든 노드를 하나하나 다 뒤져야 합니다.

이진 탐색 트리(BST) 는 여기에 단 하나의 절대 규칙(Golden Rule)을 추가하여 이 문제를 해결합니다:

BST의 절대 규칙: 어떤 노드를 기준으로 하든, 왼쪽 서브트리에 있는 모든 값은 더 작아야 하고, 오른쪽 서브트리에 있는 모든 값은 더 커야 합니다.

1. 이것이 왜 그렇게 강력할까요? (사전 효과)

사전에서 "Mango"라는 단어를 찾는다고 상상해 보세요. 1페이지, 2페이지 순서대로 읽지 않겠죠. 사전의 중간을 딱 폅니다. 만약 "Orange"가 나왔다면, "Mango"는 그 앞에 있다는 것을 알 수 있으니 사전의 오른쪽 절반은 아예 찢어서 버려도 됩니다. 단 한 번의 행동으로 해야 할 일의 50%를 제거한 것입니다.

BST가 정확히 이 역할을 합니다.

2. 핵심 연산 및 시간 복잡도

트리를 한 칸씩 내려갈 때마다 남은 노드의 절반이 날아가기 때문에, 잘 구조화된 BST는 믿을 수 없을 정도로 빠릅니다.

• 탐색: 루트에서 시작합니다. 찾는 값이 더 작으면 왼쪽으로 가고, 크면 오른쪽으로 갑니다. 찾을 때까지 반복합니다.
• 삽입: 탐색과 완전히 같은 논리를 따릅니다. 빈 공간(null)에 도달하면 그곳에 새 노드를 배치합니다.
• 삭제: 가장 까다로운 부분입니다.
  • 리프 노드(자식 0개)를 지울 때: 그냥 지우면 됩니다.
  • 자식이 1개인 노드를 지울 때: 부모 노드를 손자 노드와 직접 연결해 줍니다.
  • 자식이 2개인 노드를 지울 때: 해당 노드의 "중위 후속자(In-order Successor, 오른쪽 서브트리에서 가장 작은 값)"를 찾아 노드의 값을 그 후속자의 값으로 덮어씌운 뒤, 기존의 후속자 노드를 삭제합니다.

3부: 치명적인 결함과 해결책

위 표에서 "최악의 경우" 시간 복잡도가 $O(n)$인 것을 눈치채셨나요? 왜 그럴까요?

"퇴화된(Degraded)" 트리 문제

이미 정렬된 순서대로 숫자를 BST에 삽입한다고 상상해 보세요: 1, 2, 3, 4, 5.

• 1이 루트가 됩니다.
• 2는 더 크니까 오른쪽으로 갑니다.
• 3도 더 크니까 오른쪽으로 갑니다.

이제 이것은 나뭇가지처럼 뻗어 나가는 트리가 아니라, 오른쪽으로만 길게 늘어진 연결 리스트(Linked List) 가 되어버립니다. "사전 효과"는 완전히 사라졌습니다. 5를 찾으려면 모든 노드를 다 거쳐야만 합니다 ($O(n)$).

해결책: 자가 균형 트리 (Self-Balancing Trees)

이 문제를 방지하기 위해, 엔지니어들은 데이터를 삽입/삭제할 때 스스로 균형을 맞추는 진화된 버전의 BST를 발명했습니다. 트리의 한쪽이 너무 무거워지면, 수학적인 "회전(Rotation)"을 수행하여 루트를 끌어내리고 자식을 밀어 올려서 균형을 복구합니다.

• AVL 트리: 매우 엄격하게 균형을 유지합니다. 데이터를 읽는(Read) 작업이 많은 시스템에 적합합니다.
• 레드-블랙 트리 (Red-Black Tree): 약간 느슨하게 균형을 유지합니다. 데이터를 쓰는(Write/Insert) 작업이 많은 시스템에 유리합니다. (Java의 TreeMap과 HashMap이 내부적으로 바로 이 레드-블랙 트리를 사용합니다!).

references